/**
 * 工具类。保存图中位置占用情况，和计算可用位置
 */
import Movement from './movement'
import Position from './position'
import $ from 'jquery'

class Slots {

    constructor(graph) {
        this.graph = graph
        this.init()
    }

    init() {
        this.clear()
    }

    /****** 以下封装了slot数据结构 ******/
    // 要修改数据结构只需要修改这些方法
    // array has a maximum size of 128 * 128
    clear() {
        this.size = 128
        this.slots = new Array(this.size)
        for (let i = 0; i < this.size; i++) {
            this.slots[i] = new Array(Math.ceil(this.size / 32))
            for (let j = 0; j < this.slots[i].length; j++) {
                this.slots[i][j] = 0
            }
        }
        this._maxX = 0
        this._maxY = 0
    }

    empty(x, y) {
        let xi = x >> 5,
            xj = x & 31
        this.slots[y][xi] = this.slots[y][xi] & (0xff ^ (1 << xj))
    }

    isEmpty(x, y) {
        let xi = x >> 5,
            xj = x & 31
        return !(this.slots[y][xi] & 1 << xj)
    }

    fill(x, y) {
        if (typeof x === 'object') {
            y = x.y
            x = x.x
        }
        let xi = x >> 5,
            xj = x & 31
        this.slots[y][xi] = this.slots[y][xi] | (1 << xj)
        this._maxX = Math.max(this.maxX, x)
        this._maxY = Math.max(this.maxY, y)
    }

    isEmptyColumn(x) {
        let xi = x >> 5,
            xj = x & 31
        for (let i in this.slots) {
            if (this.slots[i][xi] & 1 << xj) {
                return false
            }
        }
        return true
    }

    isEmptyRow(y) {
        for (let i in this.slots[y]) {
            if (this.slots[y][i] !== 0) {
                return false
            }
        }
        return true
    }

    isOutOfRange(x) {
        return x < 0 || x > this.size - 1
    }

    cloneSlots() {
        return $.extend(true, [], this.slots)
    }

    setSlots(slots) {
        this.slots = slots
    }
    /****** 以上 ******/

    isEmptyArea(x1, y1, x2, y2) {
        let startX = Math.min(x1, x2),
            endX = Math.max(x1, x2),
            startY = Math.min(y1, y2),
            endY = Math.max(y1, y2)
        for (let i = startY; i <= endY; i++) {
            for (let j = startX; j <= endX; j++) {
                if (!this.isEmpty(j, i)) {
                    return false
                }
            }
        }
        return true
    }

    get maxX() {
        return this._maxX
    }

    get maxY() {
        return this._maxY
    }

    /**
     * 有水平连线穿过该位置
     * @param {int} x 
     * @param {int} y 
     */
    hasCrossingLine(x, y) {
        let left = -this.size,
            right = -this.size
        for (let i = x - 1; i >= 0; i--) {
            if (!this.isEmpty(i, y)) {
                left = i
                break
            }
        }
        for (let i = x + 1; i < this.size; i++) {
            if (!this.isEmpty(i, y)) {
                right = i
                break
            }
        }
        if (left + right > 0) {
            let node1 = this.graph.findElementViewByPosition(left, y),
                node2 = this.graph.findElementViewByPosition(right, y)

            return node1 && node2 && !!this.graph.findLinkView({
                startId: node1.id,
                endId: node2.id
            })
        }
        return false
    }

    /**
     * 移动
     * @param {Array[Movement]} movements 
     */
    move(movements) {
        for (let i in movements) {
            this.empty(movements[i].element.x, movements[i].element.y)
        }
        for (let i in movements) {
            this.fill(movements[i].element.x + movements[i].dx, movements[i].element.y + movements[i].dy)
        }

        this._maxX = 0
        this._maxY = 0
        for (let i = this.size - 1; i > -1; i--) {
            if (!this.isEmptyRow(i)) {
                this._maxY = i
                break
            }
        }
        for (let i = this.size - 1; i > -1; i--) {
            if (!this.isEmptyColumn(i)) {
                this._maxX = i
                break
            }
        }
    }

    /**
     * 最左侧插入节点时，计算返回一个可用位置
     */
    calculateLeftSlot() {
        for (let i = this.slots.length - 1; i > -1; i--) {
            if (this.isEmpty(0, i) && (i == 0 || !this.isEmpty(0, i - 1))) {
                return {
                    add: new Position(0, i)
                }
            }
        }
        return {
            error: 'outofrange'
        } // no available slot
    }

    /**
     * 插入一个新节点时，根据传入值计算可用位置。
     * 返回插入节点的位置以及其他节点需要如何移动
     * case 1. 若传入所有参数，则根据两个点来决定新的点位置
     * case 2. 若只传入x1，y1，则根据一个点来决定新点位置
     * @param {Number} x1 
     * @param {Number} y1 
     * @param {Number} x2 
     * @param {Number} y2 
     * @return 返回 {add: 新节点坐标, move: [现有节点移动规则]}
     */
    calculateNewSlot(x1, y1, x2, y2) {
        var x = (x2 !== undefined ? Math.max(x1, x2) : x1) + 1,
            minX = Math.min(x1, x2),
            yWithMinX = x1 < x2 ? y1 : y2,
            downAtFirst = y2 === undefined || y2 >= y1 ? 1 : 0,
            startY = y1,
            iter = 0 + ((y1 === y2) ? 1 : 0), // 迭代次数。两个点在同一行则迭代次数加1，避免新节点与他们同行
            tested = 0 // 验证次数
        while (tested < this.size) {
            // 节点右一列上下跳动选择空位置
            var y = startY + Math.ceil(iter / 2) * Math.pow(-1, iter + downAtFirst)
            iter++
            if ((y < 0 && !this.isEmpty(x, this.size - 1)) || y >= this.size) {
                continue
            } else {
                tested++
            }
            if (y < 0) { // 顶部插入新行
                let result = {
                    add: new Position(x, 0)
                }
                let move = []
                for (let i in this.graph.elemView) {
                    move.push(new Movement(this.graph.elemView[i], 0, 1))
                    if (this.isOutOfRange(this.graph.elemView[i].y + 1)) {
                        return {
                            error: 'outofrange'
                        }
                    }
                }
                result.move = move
                return result
            }
            if (this.isEmpty(x, y) &&
                !this.hasCrossingLine(x, y) && // 没有横线穿过该节点
                (y != yWithMinX || this.isEmptyArea(x, y, minX + 1, y))) { // 和源节点平行则需要和源节点之间没有节点
                if (this.isOutOfRange(x)) {
                    return {
                        error: 'outofrange'
                    }
                }
                return {
                    add: new Position(x, y)
                }
            }
        }
    }

    /**
     * 在指定节点后插入清理，该节点后续节点成为清理节点的后续
     * @param {Element} startElement
     */
    calculateInsertSlot(startElement) {
        let successors = this.graph.succeedingElements(startElement, true)

        let cloned = this.cloneSlots()
        // 忽略后继点，计算插入位置
        for (let i in successors) {
            this.empty(successors[i].x, successors[i].y)
        }
        let newSlot = this.calculateNewSlot(startElement.x, startElement.y)
        if (newSlot.error) {
            return newSlot
        }
        newSlot.move = newSlot.move || []
        if (newSlot.move.length > 0) { // 有且只可能是下移动作，则后续点也要下移
            for (let i in successors) {
                newSlot.move.push(new Movement(successors[i].x, 0, 1))
            }
        }
        this.setSlots(cloned)

        // 后续节点与起始点列相邻，则需要右移
        let flag = this.graph.succeedingElements(startElement, false).reduce((p, e) => {
            return p || e.x == startElement.x + 1
        }, false)
        if (flag) {
            let successorsMove = this._calculateMoveRightSlot(successors, 1)
            if (successorsMove.error) {
                return successorsMove
            }
            newSlot.move = newSlot.move.concat(successorsMove.move)
        }
        return newSlot
    }

    /**
     * 重新连线后，后者列若小于等于前置点的列，则需要调整
     * @param {Element} startElement 
     * @param {Element} endElement 
     */
    calculateRelinkSlot(startElement, endElement) {
        if (endElement.x > startElement.x) { // 列在后，不用处理
            return {}
        }
        let dx = startElement.x - endElement.x + 1
        let successors = this.graph.succeedingElements(endElement, true)
        successors.unshift(endElement) // add self

        return this._calculateMoveRightSlot(successors, dx)
    }

    _calculateMoveRightSlot(elementsToMove, dx) {
        let move = []

        // 复制一份slot
        let cloned = this.cloneSlots()
        // 清空要移动的slot
        for (let i in elementsToMove) {
            this.empty(elementsToMove[i].x, elementsToMove[i].y)
        }
        for (let i in elementsToMove) {
            // 目标位被占，则再往后移一格
            while (!this.isEmpty(elementsToMove[i].x + dx, elementsToMove[i].y)) {
                dx++
            }
            if (this.isOutOfRange(elementsToMove[i].x + dx)) {
                return {
                    error: 'outofrange',
                }
            }
            // 当前点占位
            this.fill(elementsToMove[i].x + dx, elementsToMove[i].y)
            move.push(new Movement(elementsToMove[i], dx, 0))
        }

        // 还原slot
        this.setSlots(cloned)
        return {
            move: move
        }
    }

    /**
     * 移除一个节点后，若出现空行或空列，则消除之
     * @param {Element} removedElement 
     */
    calculateRemoveSlot(removedElement) {
        let x = removedElement.x,
            y = removedElement.y,
            emptyY = this.isEmptyRow(y),
            emptyX = this.isEmptyColumn(x),
            notFirstColumn = removedElement.x != 0,
            move = []
        for (let i in this.graph.elemView) {
            let dx = 0,
                dy = 0
            if (emptyY && this.graph.elemView[i].y > y) {
                dy = -1
            }
            if (emptyX && notFirstColumn && this.graph.elemView[i].x > x) {
                dx = -1
            }
            if (dx != 0 || dy != 0) {
                move.push(new Movement(this.graph.elemView[i], dx, dy))
            }
        }
        return {
            move: move
        }
    }
}

export default Slots